package de.pass.ch.dijkstra;

import de.pass.ch.datastr.BinaryHeap;
import de.pass.ch.datastr.IntArrayGrowable;
import de.pass.ch.datastr.PQueueNode;
import de.pass.ch.graph.UpdateableGraph;
import de.pass.ch.graph.node.CurrentNode;
import de.pass.ch.graph.node.INode;
import de.pass.ch.util.Constants;

public class DijkstraUpdateVoronoi extends AbstractDijkstra<PQueueNode> {

	@SuppressWarnings("unchecked")
	public DijkstraUpdateVoronoi(UpdateableGraph graph) {

		super(graph, new IntArrayGrowable[2], new BinaryHeap[2]);

		_settledNodes[0] = new IntArrayGrowable(100);
		_settledNodes[1] = null;

		_pqueue[0] = new BinaryHeap<PQueueNode>(500, new PQueueNode());
		_pqueue[1] = null;

		_searchDirections = 1;
	}

	/**
	 * Insert a node with given distance and parent into the priority queue.
	 * Used to update shortest paths based Voronoi regions.
	 */
	public void insertNode(int node, int dist, int parent) {
		int index = insert(0, dist, node, new PQueueNode());
		pqData(0, index).updateParent(parent, Constants.SPECIAL_NODEID);
	}

	/**
	 * Perform a single step of Dijkstra's algorithm. The topmost node in the
	 * priority queue is deleted and returned (call-by-reference). Used to
	 * update shortest paths based Voronoi regions.
	 */
	public boolean searchNext(int node, int dist, int parent) {
		CurrentNode u = new CurrentNode();
		if (!_pqueue[0].empty()) {

			// *** deleteMin ***
			deleteMin(0, u);

			node = u.nodeID;
			dist = u.dist;
			parent = pqData(0, u.index).parentNode();

			return true;
		}
		return false;
	}

	/**
	 * Insert or update a node with given distance and parent into the priority
	 * queue. Used to update shortest paths based Voronoi regions.
	 */
	public void updateNode(int node, int dist, int parent) {
		int e = isReached(node);
		if (e == 0) {
			// v has been unreached -> INSERT it
			e = insert(0, dist, node, new PQueueNode());
		} else {
			// v has been reached -> try to DECREASE its KEY
			e = decreaseKey(0, dist, node);
		}
		if (e != 0) {
			// if the pqueue operation/the relaxation of the edge was successful
			// COUNTING( counter.incDouble(COUNT_RELAXED_EDGES_SUCCESS) );

			PQueueNode data = pqData(0, e);
			// update the parent of the node v
			data.updateParent(parent, Constants.SPECIAL_NODEID);
		}
	}

	/** Clears the search in order to be able to start a new search. */
	public void clear() {

		processUnsettledNodes(0);

		clearNodeVector(0, 100);

		_pqueue[0] = new BinaryHeap<PQueueNode>(500, new PQueueNode());
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is reached; returns 0, otherwise.
	 */
	public int isReached(int vID) {
		return isReached(_graph.node(vID));
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is reached; returns 0, otherwise.
	 */
	public int isReached(INode v) {
		int index = v.getPQElement();
		if (index == 0)
			return 0;
		if (_pqueue[0].isDummy(index))
			return 0;
		return index;
	}

}
